Corporate flight bookings [Line Sweep]

Time: O(N); Space: O(1); medium

There are N flights, and they are labeled from 1 to N. We have a list of flight bookings. The i-th booking bookings[i] = [i, j, k] means that we booked k seats from flights labeled i to j inclusive.

Return an array answer of length N, representing the number of seats booked on each flight in order of their label.

Example 1:

Input: bookings =

[
    [1, 2, 10],
    [2, 3, 20],
    [2, 5, 25]
]

N = 5 Output: [10, 55, 45, 25, 25]

Notes:

• 1 <= len(bookings) <= 20000

• 1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000

• 1 <= bookings[i][2] <= 10000

class Solution1(object):
    def corpFlightBookings(self, bookings, N):
        """
        :type bookings: List[List[int]]
        :type n: int
        :rtype: List[int]
        """
        result = [0] * (N + 1)
        for i, j, k in bookings:
            result[i - 1] += k
            result[j] -= k
        for i in range(1, len(result)):
            result[i] += result[i - 1]
        result.pop()
        return result

s = Solution1()
bookings = [
    [1, 2, 10],
    [2, 3, 20],
    [2, 5, 25]
]
N = 5
assert s.corpFlightBookings(bookings, N) == [10, 55, 45, 25, 25]

See also:

https://leetcode.com/problems/corporate-flight-bookings